package manaul;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class C1_30 {

	public static int euclid(int p, int q) {
		//System.out.println("p = " + p + ", q = " + q);
		if (p == 0 || q == 0) {
			return 1;
		}
		if (p < q) {
			int t = p;
			p = q;
			q = t;
		}
		if (p % q == 0) {
			return q;
		} else {
			return euclid(q, p % q);
		}
	}

	public static void main(String[] args) {
		System.out.println("result: " + euclid(105, 24));
		System.out.println("result: " + euclid(1111111, 1234567));
		int N=StdIn.readInt();
		boolean[][] m=new boolean[N][N];
		for (int i = 0; i < m.length; i++) {
			for (int j = 0; j < m.length; j++) {
				if (euclid(i, j)==1) {
					m[i][j]=true;
				}
				else {
					m[i][j]=false;
				}
				
			}
		}
		for (int i = 0; i < m.length; i++) {
			
			for (boolean q:m[i])
				
				StdOut.print(" "+q);
			StdOut.print("\n");
		}
		
	}

}
